\subsection{On maximizing the number of releases in each execution region}
\label{sec:example2}

In the previous section, we proved that the critical instant for a self-suspending task $\sstask$ suffering interference from non-self-suspending sporadic tasks happens when every higher priority task releases a job synchronously with at least one execution region of $\sstask$. Let us now define a set of synchronous release constraints $\synch{}$ as follows.
\begin{definition}[Set of synchronous release constraints]
Let $\synch{j}$ be a set of tasks in $\hp{ss}$ that are constrained to release a job synchronously with the $j^\text{th}$ execution region of $\sstask$. Then, the set of synchronous release constraints $\synch{}$ is the composition of the sets $\synch{j}$ associated with every execution region $\ssregion{j}$ of $\sstask$. It  thus represents the release constraints imposed to each of the tasks in $\hp{ss}$ with respect to the execution regions of $\sstask$. %One and one only release constraint must be enforced for each task in $\hp{ss}$.
\end{definition}

With the above definition, we now prove the counter-intuitive property that, even considering the set of synchronous releases that lead to the critical instant of $\sstask$, the WCRT of $\sstask$ is not always obtained when the higher priority tasks release as many jobs as possible in each execution region of $\sstask$.

\begin{lemma}
\label{lem:ex2}
Let $\synch{}$ be a set of synchronous release constraints on tasks in $\hp{ss}$. Releasing the jobs of the tasks in $\hp{ss}$ as often as possible in each execution region of $\sstask$, while respecting the set of constraints $\synch{}$, will not always lead to the WCRT of $\sstask$ under $\synch{}$.
\end{lemma}
\begin{proof}
%The lemma is proved by contradiction --- that is, that releasing as many jobs as possible in each execution region of $\sstask$, while respecting the set of constraints $\synch{}$, does always lead to the WCRT of $\sstask$ under $\synch{}$ ---  is false. This can be proved with the following counter-example;
Consider a task set $\tau=\left\{\tau_1, \tau_2, \tau_3, \sstask\right\}$ of $4$ tasks in which $\tau_1$, $\tau_2$ and $\tau_3$ are non-self-suspending sporadic tasks and $\sstask$ is a self-suspending task with the lowest priority. The tasks are characterized as follows: $\tau_1 = \left\langle \left(4\right), 8, 8\right\rangle$, $\tau_2 = \left\langle \left(1\right), 10, 10\right\rangle$, $\tau_3 = \left\langle \left(1\right), 17, 17\right\rangle$ and $\sstask = \left\langle \left(265, 2, 6\right), 1000, 1000\right\rangle$. The set $\synch{}$ imposes $\tau_1$ to release a job synchronously with the second execution region $\ssregion{2}$ of $\sstask$ while $\tau_2$ and $\tau_3$ must release a job synchronously with $\ssregion{1}$.

Consider two scenarios with respect to the job release pattern, always respecting the given synchronous release constraints. In Scenario 1, the jobs of the higher priority non-self-suspending tasks are released as often as possible in each execution region of $\sstask$. In Scenario~2 however, one less job of task $\tau_1$ is released in (and therefore interfere with) $\ssregion{1}$. Showing that the WCRT of the self-suspending task in Scenario 2 is higher than that of Scenario 1 proves the claim. %We provide such an example next.

%Consider a processor $\pi$ and a taskset $\tau = {\tau_1, \tau_2, \tau_3, \tau_{ss}}$ of $4$ tasks in which $\tau_{ss}$ is the self-suspending task and $\tau_1$, $\tau_2$ and $\tau_3$ are non-self-suspending tasks. The tasks are characterized as shown in Table~ref{tab:ex2}. As can be seen, the priority of all the three non-self-suspending tasks is higher than that of the self-suspending task. Also, for ease of explanation, let the synchronous release constraint be as follows. 
%A job of task $\tau_2$ and a job of $\tau_3$ are released synchronously with the first execution segment of task $\tau_{ss}$ (at time $0$) and a job of task $\tau_1$ is released synchronously with the second execution segment of task $\tau_{ss}$ (a close observation would reveal that a job of $\tau_1$ is released synchronously with the first execution segment of $\tau_{ss}$ as well; however, this is just a coincidence).

%A job of each of the three non-self-suspending tasks is released synchronously with the first execution segment of task $\tau_{ss}$ (at time $0$). and a job of task $\tau_1$ is released synchronously with the second execution segment of task $\tau_{ss}$ (a close observation would reveal that a job of $\tau_1$ is released synchronously with the first execution segment of $\tau_{ss}$ as well; however, this is just a coincidence).
%\begin{table}[!t]
%\begin{center}
%\begin{tabular}{|c||c|}
%	\hline
%	  \textbf{Task} & \textbf{Parameters of task} \\ \hline \hline
%    $\tau_1$      & $\left\langle \left(4\right), 8, 8\right\rangle$  \\ \hline
%    $\tau_2$      & $\left\langle \left(1\right), 10, 10\right\rangle$ \\ \hline
%    $\tau_3$      & $\left\langle \left(1\right), 17, 17\right\rangle$ \\ \hline
%    $\tau_{ss}$   & $\left\langle \left(265, 2, 6\right), \infty, \infty\right\rangle$ \\ \hline
%\end{tabular}
%\end{center}
%\caption{Example task set.}
%\label{tab:ex2}
%\end{table}

Scenario~1 is depicted in Fig.~\ref{fig:ex2sc1}, and Scenario~2 in Fig.~\ref{fig:ex2sc2}. The first $765$ time units are omitted in both figures. This is mainly due to space constraint. Furthermore, in both scenarios the release and schedule of the jobs is identical in this time window. % and further this time window is not relevant in the context of the claim. 
A first job of $\tau_1$, $\tau_2$ and $\tau_3$ is released synchronously with the arrival of the first execution region of $\sstask$ at time $0$. The subsequent jobs of these three tasks are released as often as possible respecting the minimum inter-arrival times of the respective tasks. That is, they are released periodically with periods $T_1$, $T_2$ and $T_3$, respectively. With this release pattern, it is easy to compute that the $97^\text{th}$ job of $\tau_1$ is released at time $768$, the $78^\text{th}$ job of $\tau_2$ at time $770$ and the $46^\text{th}$ job of $\tau_3$ at time $765$. As a consequence, at time $765$, $\tau_{ss}$ has finished executing $259$ time units of its first execution segment out of $265$ (indeed, we have $765 - 96 \times 4 - 77 \times 1 - 45 \times 1 = 259$) in both scenarios. From time $765$ onwards, we separately consider Scenario~1 and~2.
\begin{figure}
  \centering
  \subfloat[Scenario 1. Jobs are released as often as possible while respecting all the constraints on the synchronous releases.]{\label{fig:ex2sc1} \includegraphics[height=1.95cm, width=\linewidth]{ex2sc1}} \\
  \subfloat[Scenario 2. Jobs are not released as often as possible.]{\label{fig:ex2sc2} \includegraphics[height=1.8cm, width=\linewidth]{ex2sc2}}
  \caption{Example showing that releasing higher priority jobs as often as possible while respecting a set of synchronous release constraints $\synch{}$ on tasks in $\hp{ss}$ may not always cause the maximum interference on a self-suspending task $\sstask$.}
  \label{fig:ex2}
\end{figure}

\noindent\textbf{Scenario 1.} Continuing the release of jobs of the non-self-suspending tasks as often as possible without violating their minimum inter-arrival times, the first execution region $\ssregion{1}$ of $\tau_{ss}$ finishes its execution at time $782$ as shown in Fig.~\ref{fig:ex2sc1}. After completion of its first execution region, $\sstask$ self-suspends for two time units until time $784$. As $\tau_3$ would have released a job just after the completion of $\ssregion{1}$, we delay the release of that job from time $782$ to $784$ in order to maximize the interference exerted by $\tau_3$ on the second execution region of $\sstask$ as shown in Fig.~\ref{fig:ex2sc1}. Note that, in order to respect its minimum inter-arrival time, $\tau_2$ has an offset of $6$ time units with the arrival of the second execution region of $\sstask$. Upon following the rest of the schedule, it can easily be seen that the job of $\tau_{ss}$ finishes its execution at time $800$.

\noindent\textbf{Scenario 2.} As shown on Fig.~\ref{fig:ex2sc2}, the release of a job of task $\tau_1$ is skipped at time $776$ in comparison to Scenario~1. As a result, the execution of $\ssregion{1}$ is completed at time $777$, thereby causing one job of $\tau_2$ that was released at time $780$ in Scenario 1, to \emph{not} be released during the execution of the first execution region of $\tau_{ss}$ in Scenario~2. The response time of $\ssregion{1}$ is thus reduced by $C_1 + C_2 = 5$ time units in comparison to Scenario 1 (see Fig.~\ref{fig:ex2}). Note that this deviation from Scenario 1 still allows us to respect the synchronous release constraints imposed by $\synch{}$, as we can release the next job of $\tau_1$ synchronously with the second execution region of $\tau_{ss}$ without violating the minimum inter-arrival time of $\tau_1$. The next job of $\tau_3$ however, is not released in the suspension region anymore but $3$ time units after the arrival of $\ssregion{2}$. Moreover, the offset of $\tau_2$ with respect to the start of the second execution region is reduced by $C_1 + C_2 = 5$ time units. This causes an extra job of $\tau_2$ to be released in the second execution region of $\tau_{ss}$, initiating a cascade effect: an extra job of $\tau_1$ is released in $\ssregion{2}$, which in turn causes the release of an extra job of $\tau_3$, itself causing the arrival of one more job of $\tau_2$ in the second execution region of $\tau_{ss}$. Consequently, the response time of $\ssregion{2}$ increases by $C_2 + C_1 + C_3 + C_2 = 7$ time units. Overall, the response time of $\tau_{ss}$ increases by $7 - 5 = 2$ time units in comparison to Scenario~1. This is reflected in Figure~\ref{fig:ex2sc2} as the job of $\tau_{ss}$ finishes its execution at time $802$.

This counter-example proves that the response time of a self-suspending task $\tau_{ss}$ can be larger when the tasks in $\hp{ss}$ do not release jobs as often as possible.
\end{proof}

\begin{theorem}
The WCRT of $\sstask$ is not always obtained when the tasks in $\hp{ss}$ release their jobs as often as possible in the execution regions of $\sstask$ under any set of constraints $\synch{}$ on their synchronous releases.
\end{theorem}
\begin{proof}
Using the task set $\tau$ of the counter-example provided in Lemma~\ref{lem:ex2}, one can check that the response-time obtained for $\sstask$ when releasing jobs as often as possible, while respecting any combination of constraints on the synchronous releases of the tasks in $\hp{ss}$, never exceeds $800$ (note that $4$ of the $8$ possible combinations are already covered by Scenario 1 of the Fig.~\ref{fig:ex2} since $\tau_1$ and $\tau_3$ have a synchronous release with both execution regions of $\sstask$). However, it was shown in the proof of Lemma~\ref{lem:ex2} that a response time of $802$ can be experienced by $\sstask$ when the release of one job of $\tau_1$ is delayed. This proves the theorem. 
\end{proof}

